public class Solution4 {
    //LCR 091. 粉刷房子
    public int minCost(int[][] costs) {
        int n = costs.length;
        int ret = 0;
        if (n == 1) {
            ret = Math.min(costs[0][0],costs[0][1]);
            return Math.min(ret,costs[0][2]);
        }

        int[] f = new int[n];
        int[] g = new int[n];
        int[] h = new int[n];
        f[0] = costs[0][0];
        g[0] = costs[0][1];
        h[0] = costs[0][2];
        f[1] = costs[1][0];
        g[1] = costs[1][1];
        h[1] = costs[1][2];

        for (int i = 2; i < n; i++) {
            f[i] = Math.min(g[i-1]+h[i-2],h[i-1]+g[i-2]) + costs[i][0];
            g[i] = Math.min(f[i-1]+h[i-2],h[i-1]+f[i-2]) + costs[i][1];
            h[i] = Math.min(f[i-1]+g[i-2],g[i-1+f[i-2]]) + costs[i][2];
        }
        ret = Math.min(f[n-1],g[n-1]);
        return Math.min(ret,h[n-1]);
    }
}
